package com.sicheng.lc.周赛.分类.dp;

import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/2 15:40
 */
public class 解决智力问题 {
    //todo
    //https://leetcode.cn/problems/solving-questions-with-brainpower/
    static int[] st = new int[(int) (1e5 + 10)];
    static long[][] dp = new long[(int) (1e5 + 10)][2];

    public long mostPoints(int[][] questions) {
        Arrays.fill(st, 0, questions.length, -1);
        dp[0][1] = questions[0][0];
        st[questions[0][1] + 1] = 0;
        for (int i = 1; i < dp.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            if (st[i] >= 0)
                dp[i][1] = Math.max(dp[st[i]][0], dp[st[i]][1]) + questions[i][0];
            else {
                dp[i][1] = dp[i - 1][0] + questions[i][0];
            }
            st[questions[i][1] + 1] = i;
        }

        return Math.max(dp[questions.length - 1][0], dp[questions.length - 1][1]);
    }

    public static void main(String[] args) {
        解决智力问题 s = new 解决智力问题();
        int[][] q = {};
        System.out.println(s.mostPoints(q));
    }
}
